/*
 * @lc app=leetcode.cn id=432 lang=cpp
 *
 * [432] 全 O(1) 的数据结构
 *
 * https://leetcode.cn/problems/all-oone-data-structure/description/
 *
 * algorithms
 * Hard (47.13%)
 * Likes:    274
 * Dislikes: 0
 * Total Accepted:    26.5K
 * Total Submissions: 56.3K
 * Testcase Example:  '["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]\n' +
  '[[],["hello"],["hello"],[],[],["leet"],[],[]]'
 *
 * 请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
 *
 * 实现 AllOne 类：
 *
 *
 * AllOne() 初始化数据结构的对象。
 * inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
 * dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key
 * 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
 * getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
 * getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。
 *
 *
 * 注意：每个函数都应当满足 O(1) 平均时间复杂度。
 *
 *
 *
 * 示例：
 *
 *
 * 输入
 * ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey",
 * "getMinKey"]
 * [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
 * 输出
 * [null, null, null, "hello", "hello", null, "hello", "leet"]
 *
 * 解释
 * AllOne allOne = new AllOne();
 * allOne.inc("hello");
 * allOne.inc("hello");
 * allOne.getMaxKey(); // 返回 "hello"
 * allOne.getMinKey(); // 返回 "hello"
 * allOne.inc("leet");
 * allOne.getMaxKey(); // 返回 "hello"
 * allOne.getMinKey(); // 返回 "leet"
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= key.length <= 10
 * key 由小写英文字母组成
 * 测试用例保证：在每次调用 dec 时，数据结构中总存在 key
 * 最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 10^4 次
 *
 *
 */

// @lc code=start
#include <iostream>
#include <list>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
/* struct isSmaller {
    bool operator()(const pair<string, int> &item1, const pair<string, int> &item2) {
        return item1.second < item2.second;
    }
};
struct isBigger {
    bool operator()(const pair<string, int> &item1, const pair<string, int> &item2) {
        return item1.second > item2.second;
    }
}; */

class AllOne {
private:
    // list为双向链表，每个节点包含int和一个string类型的set集合
    // int指示该节点中所存key出现的次数
    // set存储了该节点内出现次数相同，都为该int值的string的集合
    list<pair<unordered_set<string>, int>> doubleList;
    // hash表存储了key以及该字符串所对应出现次数的双向链表的节点（迭代器形式，方便直接访问）
    unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> hash;

public:
    AllOne() {}

    void inc(string key) {
        // hash表中有key
        if (hash.count(key)) {
            // cur为当前key所在的迭代器，nxt为下一个迭代器
            auto cur = hash[key], nxt = next(cur);
            // 如果nxt为end()，或者nxt数值比cur+1大，则需要新建节点
            if (nxt == doubleList.end() || nxt->second > cur->second + 1) {
                unordered_set<string> s{key};
                // 插入到nxt前面
                hash[key] = doubleList.emplace(nxt, s, cur->second + 1);
            }
            // cur+1的节点已存在，刚好是nxt
            else {
                nxt->first.emplace(key);
                hash[key] = nxt;
            }
            // cur节点里删除key
            cur->first.erase(key);
            // 如果此时cur节点为空，删除cur
            if (cur->first.empty()) {
                doubleList.erase(cur);
            }
        }
        // hash表中无key，则需要加入到链表中，并且出现次数为1
        else {
            // 如果链表为空，或者第一个节点次数不为1，则需要新建链表节点
            if (doubleList.empty() || doubleList.begin()->second > 1) {
                unordered_set<string> s{key};
                // 插入到链表最前端
                doubleList.emplace_front(s, 1);
            }
            // 链表第一个节点出现次数为1
            else {
                doubleList.begin()->first.emplace(key);
            }
            hash[key] = doubleList.begin();
        }
    }

    void dec(string key) {
        // key当前所在节点
        auto cur = hash[key];
        // key仅出现一次，将其移出hash
        if (cur->second == 1) {
            hash.erase(key);
        }
        // key出现多次
        else {
            // cur为key当前节点迭代器，pre为前一个迭代器
            auto pre = prev(cur);
            // 如果cur就是第一个节点，或者pre比cur-1还要小，那么需要新建一个链表节点
            if (cur == doubleList.begin() || pre->second < cur->second - 1) {
                unordered_set<string> s{key};
                // 插入到cur前
                hash[key] = doubleList.emplace(cur, s, cur->second - 1);
            }
            // 已经存在cur-1的节点，那就是pre
            else {
                pre->first.emplace(key);
                hash[key] = pre;
            }
        }
        // cur节点里把key删除
        cur->first.erase(key);
        // 如果删除key之后cur为空，那么需要把该链表节点删除
        if (cur->first.empty()) {
            doubleList.erase(cur);
        }
    }

    string getMaxKey() {
        // 如果链表非空，返回尾节点的任意一个string
        return doubleList.empty() ? "" : *doubleList.rbegin()->first.begin();
    }

    string getMinKey() {
        // 如果链表非空，返回头节点的任意一个string
        return doubleList.empty() ? "" : *doubleList.begin()->first.begin();
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */
// @lc code=end
